#pragma once
#include<iostream>
#include<vector>
#include<utility>
using namespace std;

template<class k,class v>
class HashNode
{
public:
	HashNode(const pair<k, v>& pr = pair<k, v>())
		:pa(pr)
		,next(nullptr)
	{}

	pair<k, v> pa;
	HashNode* next;
};

template<class k>
class HashFun
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};

template<>
class HashFun<string>
{
public:
	size_t operator()(const string& key)
	{
		size_t hashv = 0;
		for (auto ch : key)
		{
			hashv *= 131;
			hashv += ch;
		}

		return hashv;
	}
};


template<class k,class v,class HashFunction = HashFun<k>>
class BucketHash
{
public:
	typedef HashNode<k, v> Node;

	BucketHash()
	{
		_table.resize(5, nullptr);
		_size = 0;
	}

	bool insert(const pair<k, v>& value)
	{
		HashFunction hf;
		if (_size == _table.size())
		{
			size_t _capacity = _table.size() * 2;
			vector<Node*> NewTable(_capacity, nullptr);

			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* Next = cur->next;

					size_t pos = hf(cur->pa.first) % _capacity;
					cur->next = NewTable[pos];
					NewTable[pos] = cur;

					cur = Next;
				}
			}

			_table.swap(NewTable);
		}

		size_t pos = hf(value.first) % _table.size();
		Node* cur = _table[pos];
		while (cur)
		{
			if (cur->pa.first == value.first)
			{
				return false;
			}
			cur = cur->next;
		}
		Node* NewNode = new Node(value);
		NewNode->next = _table[pos];
		_table[pos] = NewNode;
		_size++;
		return true;
	}

	Node* find(const k& key)
	{
		HashFunction hf;
		size_t pos = hf(key) % _table.size();
		Node* cur = _table[pos];
		while (cur)
		{
			if (cur->pa.first == key)
			{
				return cur;
			}
			cur = cur->next;
		}

		return nullptr;
	}

	bool erase(const k& key)	
	{
		HashFunction hf;
		size_t pos = hf(key) % _table.size();
		Node* cur = _table[pos];
		Node* prev = nullptr;
		while (cur)
		{
			if (cur->pa.first == key)
			{
				if (prev == nullptr)
				{
					Node* Next = cur->next;
					delete cur;
					_table[pos] = Next;
					_size--;
					return true;
				}
				else
				{
					Node* Next = cur->next;
					delete cur;
					prev->next = Next;
					_size--;
					return true;
				}
			}

			prev = cur;
			cur = cur->next;
		}

		return false;
	}

	~BucketHash()
	{
		for (int i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* Next = cur->next;
				delete cur;
				cur = Next;
			}
		}
	}

private:
	vector<Node*> _table;
	size_t _size;
};

